package org.hhchat.leetcode.banarySearch;

import java.util.Arrays;

public class code475_easy {
    static class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(heaters);
            int max = Integer.MIN_VALUE;
            for (int h : houses) {
                int index = binSearch(h, heaters);
                max = Integer.max(checkMinPath(h,index,heaters), max);
            }
            return max;
        }

        public int checkMinPath(int key, int index,int[] heaters) {
            if (index < 0) {
                index = -(index + 1);
            }
            int left = index > 0 ? key - heaters[index - 1] : heaters[0] - key;
            int right = index < heaters.length ? heaters[index] - key : key - heaters[heaters.length - 1];
            return Integer.min(left, right);
        }

        public int binSearch(int key, int[] heaters) {
            int l = 0;
            int h = heaters.length - 1;
            while (l <= h) {
                int mid = l + (h - l) / 2;
                if (heaters[mid] == key) {
                    return mid;
                }
                if (heaters[mid] > key) {
                    h = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
            return -(l + 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findRadius(
                new int[]{282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923},
                new int[]{823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612}));
//        System.out.println(solution.binSearch(8,new int[]{1,6,7}));
    }
}
